Search results for "bezkonteksta valoda"

Kvantu vaicājumu sarežģītība bezkonteksta gramatikām

2019

Bezkonteksta gramatikas un to ģenerētās valodas ir plaši pētīta tēma datorzinātnē. Tām ir dažādi praktiski pielietojumi, piemēram, XML valodā. Savukārt kvantu skaitļošana, it sevišķi kvantu vaicājumu algoritmi, ir datorzinātnes nozare, kas par spīti popularitātei, ir vēl neizpētīta un neskaidra. Šī darba mērķis ir aplūkot vārda piederības problēmu bezkonteksta valodai no kvantu vaicājumu algoritmu puses. Konkrētāk - darbā tika izvirzīti divi uzdevumi. Pirmais uzdevums bija atrast bezkonteksta valodu ar kvantu vaicājumu sarežģītību O(N^c), kur c0 vai pierādīt par tādas neesamību. Otrais uzdevums - uzrādīt intuitīvi saprotamu bezkonteksta valodas konstrukciju, kas ļauj konstruēt valodu ar kva…